Non-volatile storage devices have enabled increased portability of data and software applications. Non-volatile storage devices can enhance data storage density by storing multiple bits in each memory cell. For example, multi-level cell (MLC) flash memory devices provide increased storage density by storing 2 bits per cell, 3 bits per cell, 4 bits per cell, or more. Although increasing the number of bits per cell and reducing device feature dimensions may increase the storage density of a memory device, an error rate of data stored at the memory device may also increase.
Error correction coding (ECC) is often used to correct errors that occur in data read from a memory device. Prior to storage, data may be encoded by an ECC encoder to generate redundant information that may be stored with the data as an ECC codeword. Examples of ECC techniques include Bose-Chaudhuri-Hocquenghem (BCH) and Reed-Solomon techniques.
After retrieving the data, a decoding process may be performed using the redundant information to correct one or more errors that may have occurred during writing, storage, or reading of the data. The decoding process may include a Chien search to determine roots of polynomials over a finite field. The Chien search in BCH and Reed-Solomon decoding accounts for a significant part of the overall decoder power consumption, especially for long codes constructed over finite fields of high order.